package Leetcode.搜索与回溯;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/4/21 0:48
 * @Description:
 * 组合总和 III
 * 已解答
 * 中等
 * 相关标签
 * 相关企业
 * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 *
 * 只使用数字1到9
 * 每个数字 最多使用一次
 * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 *
 *
 *
 * 示例 1:
 *
 * 输入: k = 3, n = 7
 * 输出: [[1,2,4]]
 * 解释:
 * 1 + 2 + 4 = 7
 * 没有其他符合的组合了。
 * 示例 2:
 *
 * 输入: k = 3, n = 9
 * 输出: [[1,2,6], [1,3,5], [2,3,4]]
 * 解释:
 * 1 + 2 + 6 = 9
 * 1 + 3 + 5 = 9
 * 2 + 3 + 4 = 9
 * 没有其他符合的组合了。
 * 示例 3:
 *
 * 输入: k = 4, n = 1
 * 输出: []
 * 解释: 不存在有效的组合。
 * 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
 *
 *
 * 提示:
 *
 * 2 <= k <= 9
 * 1 <= n <= 60
 */

public class combinationSum3 {
    private int k;
    private final List<Integer> path = new ArrayList<>();
    private final List<List<Integer>> ans = new ArrayList<>();
    List<Integer> temp = new ArrayList<Integer>();
    public static void main(String[] args) {
        int k = 3, n = 7;

        System.out.println(new combinationSum3().combinationSum3(k, n));
    }

    /**
     * 只使用数字1到9
     * 每个数字 最多使用一次
     * 列表不能包含相同的组合两次
     * @param k
     * @param n
     * @return
     */
    public static List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>>ans = new ArrayList<>();
        if (k > n) {
            return ans;
        }
        Deque<Integer> path = new ArrayDeque<>();
        dfs(ans, 9,path, k, n);
        return ans;
    }



/*    public List<List<Integer>> combinationSum6(int k, int n) {
        dfs9(1, 9, k, n);
        return ans;
    }

    public void dfs9(int cur, int n, int k, int sum) {
        if (temp.size() + (n - cur + 1) < k || temp.size() > k) {
            return;
        }
        if (temp.size() == k) {
            int tempSum = 0;
            for (int num : temp) {
                tempSum += num;
            }
            if (tempSum == sum) {
                ans.add(new ArrayList<Integer>(temp));
                return;
            }
        }
        temp.add(cur);
        dfs9(cur + 1, n, k, sum);
        temp.remove(temp.size() - 1);
        dfs9(cur + 1, n, k, sum);
    }*/


    private static void dfs(List<List<Integer>> ans, int start,Deque<Integer> path, int k, int target) {
        int size = path.size();
        int deep = k - size;
        if (target < 0 || target > (start * 2 - deep + 1) * deep / 2) {
            return;
        }

        if (size == k) {
            ans.add(new ArrayList<>(path));
            return;
        }
        //这里大于deep-1 就好了，因为遍历到1了也会有多余的计算
        for (int i = start; i >= deep; i--) {
            path.push(i);
            dfs(ans, i - 1, path, k, target - i);
            path.pop();
        }
    }



    public List<List<Integer>> combinationSum4(int k, int n) {
        this.k2 = k;
        dfs(9, n);
        return ans;
    }

    /**
     * 1.剩余数字数目不够 i< d
     * 2.t<0
     * 3.剩余数字即使全部选最大的，和也不够 t例如i=5，还需要选 d=3个数那么如果t>5+4+3，可以直接返回
     * @param i
     * @param target
     */
    private void dfs(int i, int target) {
        int d = k2 - path.size(); // 还要选 d 个数
        //假设从i开始全选，因为这里是倒序找，
        // 我如果倒着把所有数都选完，target还大于0，那么也可以提前返回
        //这里用了一个等差数列求和公式，首项加尾项*项数除以2
        //(i * 2 - d + 1) * d / 2
        if (target < 0 || target > (i * 2 - d + 1) * d / 2) { // 剪枝
            return;
        }
        if (d == 0) {
            //上面已经判断完target小于0的情况和大于全选的情况了
            //所以就不需要判断 &&target == 0 了，优雅！
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j >= d; --j) {
            path.add(j);
            dfs(j - 1, target - j);
            path.remove(path.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum5(int k, int n) {
        this.k2 = k;
        dfs2(9, n);
        return ans;
    }

    private void dfs2(int i, int t) {
        int d = k2 - path.size(); // 还要选 d 个数
        if (t < 0 || t > (i * 2 - d + 1) * d / 2) { // 剪枝
            return;
        }
        if (d == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 不选 i
        if (i > d) {
            dfs2(i - 1, t);
        }
        // 选 i
        path.add(i);
        dfs2(i - 1, t - i);
        path.remove(path.size() - 1);
    }
    /**
     * 划分为k个相等的子集
     * 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
     * 示例 1：
     *
     * 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
     * 输出： True
     * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
     * 示例 2:
     *
     * 输入: nums = [1,2,3,4], k = 3
     * 输出: false
     */
    int[] nums;
    int len, avg, k2;
    public boolean canPartitionKSubsets(int[] _nums, int _k) {
        nums = _nums; k2 = _k;
        int tot = 0;
        for (int x : nums) tot += x;
        if (tot % k2 != 0) return false; // 可行性剪枝
        Arrays.sort(nums);
        len = nums.length; avg = tot / k2;
        return dfs(len - 1, 0, 0, new boolean[len]);
    }
    boolean dfs(int idx, int cur, int cnt, boolean[] vis) {
        if (cnt == k2) return true;
        if (cur == avg) return dfs(len - 1, 0, cnt + 1, vis);
        for (int i = idx; i >= 0; i--) {  // 顺序性剪枝
            if (vis[i] || cur + nums[i] > avg) continue;  // 可行性剪枝
            vis[i] = true;
            if (dfs(i - 1, cur + nums[i], cnt, vis)) return true;
            vis[i] = false;
            if (cur == 0) return false; // 可行性剪枝
        }
        return false;
    }
}
